/*************************************************************************
	> File Name: AVL.cpp
	> Author: 
	> Mail: 
	> Created Time: Wed 14 Aug 2024 08:44:42 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node
{
	int key, height;
	struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)
#define KEY(n) n->key
#define H(n) n->height
#define L(n) n->lchild
#define R(n) n->rchild
__attribute__((constructor))
void init_NIL() {
	NIL->key = -1;
	NIL->height = 0;
	NIL->lchild = NIL->rchild = NIL;
	return ;
}

Node *getNewNode(int key) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->key = key;
	p->height = 1;
	p->lchild = p->rchild = NIL;
	return p;
}

void updateHeight(Node *root) {
	H(root) = (H(L(root)) > H(R(root)) ? H(L(root)) : H(R(root))) + 1;
	return ;
}

Node *leftRotate(Node *root) {
	Node *new_node = root->rchild;
	root->rchild = new_node->lchild;
	new_node->lchild = root;
	updateHeight(root);
	updateHeight(new_node);
	return new_node;
}

Node *rightRotate(Node *root) {
	Node *new_node = root->lchild;
	root->lchild = new_node->rchild;
	new_node->rchild = root;
	updateHeight(root);
	updateHeight(new_node);
	return new_node;
}

Node *maintain(Node *root) {
	if(abs(H(L(root)) - H(R(root))) <= 1) return root;
	if(H(L(root)) > H(R(root))) {
		// LR 先左后右
		if(H(R(L(root))) > H(L(L(root)))) {
			root->lchild = leftRotate(root->lchild);
		}
		// LL 右
		root = rightRotate(root);
	} else {
		// RL 先右后左
		if(H(L(R(root))) > H(R(R(root)))) {
			root->rchild = rightRotate(root->rchild);
		}
		// RR 左
		root = leftRotate(root);
	}
	return root;
}

Node *insert(Node *root, int key) {
	if(root == NIL) return getNewNode(key);
	if(root->key == key) return root;
	if(key < root->key) root->lchild = insert(root->lchild, key);
	else root->rchild = insert(root->rchild, key);
	updateHeight(root);
	return maintain(root);
}

Node *preDecessor(Node *root) {
	Node *temp = root->lchild;
	while(temp->rchild != NIL) temp = temp->rchild;
	return temp;
}

Node *erase(Node *root, int key) {
	if(root == NIL) return root;
	if(key < root->key) root->lchild = erase(root->lchild, key);
	else if(key > root->key) root->rchild = erase(root->rchild, key);
	else {
		if(root->lchild == NIL || root->rchild == NIL) {
			Node *temp = (root->lchild != NIL) ? root->lchild : root->rchild;
			free(root);
			return temp;
		} else {
			Node *temp = preDecessor(root);
			root->key = temp->key;
			root->lchild = erase(root->lchild, temp->key);
		}
	}
	updateHeight(root);
	return maintain(root);
}

void preOrder(Node *root) {
	if(root == NIL) return ;
	printf("%d(%d)[%d, %d]\n", 
		KEY(root), H(root), 
		KEY(root->lchild), KEY(root->rchild)
	);
	preOrder(root->lchild);
	preOrder(root->rchild);
	return ;
}

Node *findKey(Node *root, int key) {
	if(root == NIL) return NIL;
	if(root->key == key) return root;
	if(key > root->key) return findKey(root->rchild, key);
	return findKey(root->lchild, key);
}

void clearRoot(Node *root) {
	if(root == NIL) return ;
	clearRoot(root->lchild);
	clearRoot(root->rchild);
	free(root);
	return ;
}
int main() {
	srand(time(0));
	int x;
	Node *root = NIL;
	while(~scanf("%d", &x)) {
		if(x == -1) break;
		root = insert(root, x);
	}
	preOrder(root);
	printf("\n");
	// while(~scanf("%d", &x)) {
	// 	if(x == -1) break;
	// 	root = erase(root, x);
	// 	preOrder(root);
	// }
	int arr[3] = {2, 6, 10};
	for(int i = 0; i < 3; i++) {
		if(findKey(root, arr[i]) != NIL) printf("Find %d in avl.\n", arr[i]);
		else printf("Not Found.\n");
	}
	clearRoot(root);
	return 0;
}
